package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         35,
		Discription: "搜索非递减数组中指定元素的插入位置",
		Level:       1,
		Labels: map[string]int{
			"二分查找": 1,
		},
	})
}

func SearchInsert(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left < right {
		mid := (left + right) / 2
		if nums[mid] < target {
			left = mid + 1
			continue
		}

		if nums[mid] > target {
			right = mid - 1
			continue
		}

		return mid
	}

	//先确定有没越界
	if nums[left] == target {
		return left
	}

	//易错
	if nums[left] > target {
		return left
	} else {
		return left + 1
	}
}
